Aiming at the shortage of traditional matrix completion algorithm in image reconstruction, a completion algorithm based on NonLocal self-similarity and Low Rank Matrix Approximation (NL-LRMA) was proposed. Firstly, the nonlocal similar patches corresponding to the local patches in the image were found through similarity measurement, and the corresponding grayscale matrices were vectorized to construct the nonlocal similar patch matrix. Secondly, aiming at the low-rank property of the obtained similarity matrix, Low-Rank Matrix Approximation (LRMA) was carried out. Finally, the completion results were recombined to achieve the goal of restoring the original image. Reconstruction experiments were performed on grayscale and RGB images. The results show that the average Peak Signal-to-Noise Ratio (PSNR) of NL-LRMA algorithm is 4 dB to 7 dB higher than that of the original LRMA algorithm on a classic dataset; at the same time, NL-LRMA algorithm is better than IRNN (Iteratively Reweighted Nuclear Norm), WNNM (Weighted Nuclear Norm Minimization), LRMA (Low-Rank Matrix Approximation) and other traditional algorithms in the terms of visual effect and PSNR value. In short, NL-LRMA algorithm effectively make up for the shortcomings of traditional algorithms in natural image reconstruction, so as to provide an effective solution for image reconstruction.